A key problem in the design, operation, control, and management of a communication network system is the efficient routing of traffic between various source and destination node pairs in the network. Routing determines how efficiently the resources of a communication system are used to communicate data through the system. As defined herein, "communication data" and "traffic" refer to any type of data communicated between one node of a communication system and another (e.g., voice data, fax data, control data, etc.).
The problem of routing traffic through a network arises in different types of communication systems. These include terrestrial or land-based communication networks, satellite-based wireless communication networks, or hybrid mixed-media (terrestrial as well as satellite) types of systems.
FIG. 1 illustrates a prior art simplified diagram of a communication network. For the purpose of illustration of traffic routing, FIG. 1 shows a simplified routing system having multiple nodes 2-18 and communication links 20-42. As used herein, a "route" is a series of nodes (e.g., nodes 2-18) connected by communication links (e.g., communication links 20-42) and through which information may be transferred from a source node to a destination node. To establish a communication path between any two nodes 2-18, multiple routes may be available. For example, assume node 2 is a source node and node 10 is a destination node. Table 1 illustrates a set of possible routes available from node 2 to node 10.
TABLE 1 __________________________________________________________________________ Possible Routes Between Node 2 and Node 10 __________________________________________________________________________ Route 1: 2 .fwdarw. 4 .fwdarw. 10 Route 2: 2 .fwdarw. 4 .fwdarw. 6 .fwdarw. 12 .fwdarw. 10 Route 3: 2 .fwdarw. 4 .fwdarw. 6 .fwdarw. 12 .fwdarw. 18 .fwdarw. 16 .fwdarw. 10 Route 4: 2 .fwdarw. 4 .fwdarw. 6 .fwdarw. 12 .fwdarw. 18 .fwdarw. 16 .fwdarw. 14 .fwdarw. 8 .fwdarw. 10 Route 5: 2 .fwdarw. 8 .fwdarw. 10 Route 6: 2 .fwdarw. 8 .fwdarw. 14 .fwdarw. 16 .fwdarw. 10 Route 7: 2 .fwdarw. 8 .fwdarw. 14 .fwdarw. 16 .fwdarw. 18 .fwdarw. 12 .fwdarw. 10 Route 8: 2 .fwdarw. 8 .fwdarw. 14 .fwdarw. 16 .fwdarw. 18 .fwdarw. 12 .fwdarw. 6 .fwdarw. 4 .fwdarw. 10 __________________________________________________________________________
In typical systems, a set of possible routes for communicating between a particular source node and a particular destination node (e.g., between node 2 and node 10) is defined before system operation begins. This set may or may not include all possible routes. However, if no such set is defined, the set of possible routes may be taken to be the set of all possible routes between the source node and the destination node.
In FIG. 1, suppose a system user makes a request to establish a communication path (e.g., a call request) between node 2 and node 10. The call may be set up along Route 1 (Table 1) if both link 20 and link 26 are capable of supporting the call (i.e., links 20, 26 have resources available). If either link 20 or link 26 does not have adequate resources available, then the link is considered blocked at that particular time and Route 1 cannot support communication between node 2 and node 10. If both links 20, 26 have adequate resources at that time, the call may be set up along Route 1.
Resources on links 20, 26 will be consumed for the duration of the call. After the call completes, the resources along links 20, 26 will be relinquished for new calls to use. A subsequent call request from node 2 to node 10 may be set up using Route 1. Alternatively, another of the alternate routes may support the call. For example, Route 6 (Table 1) may support the call if links 24, 34, 40, 36 have resources available to allocate for the call.
Whenever a request to set up a call from one node to another node arrives, the system must select a route from the set of choices available and set up the connection between the two nodes.
One prior art method of route selection based on a set of possible routes is a "Random Route Selection" method. To illustrate this method, consider the system shown in FIG. 1. When a request to set up a call from node 2 to node 10 arrives, the system will choose one of the choices (Route 1 . . . Route 8) at random and attempt to use that route. If adequate resources are available along that route, the call setup is successful. Otherwise, the call is blocked. The random choice is made with fixed probabilities that do not change with network traffic and load conditions.
For example, a system may have equal, fixed probabilities of choosing a particular route. Where eight routes are available, a 12.5% probability would exist that any one of the eight routes would be chosen. A system may, alternatively, have unequal, fixed probabilities that a particular route would be chosen. For example, a particular route may be preferred, thus have a higher probability of being chosen, because it contains fewer links.
Another method of route selection known in prior art is a "First Available Route Without Resequencing" method. Suppose the system of FIG. 1 receives a call request from node 2 to node 10. Each of the potential routes between node 2 and node 10 is "searched" in a fixed order. A search entails the system sending a route search control signal along a first choice (e.g., Route 1) and determining if resources are available on each link of the route. If resources are available, the call is set up along that route. Otherwise, a second choice (e.g., Route 2) is searched. The search continues until a route with adequate resources is discovered or all the routes are searched, but none have adequate resources. When no route has adequate resources, the call is blocked. This method is an exhaustive search procedure that ensures successful call setup provided a route with adequate resources is available.
Typical routing solutions as described above do not provide adequate service for a number of reasons. The Random Route Selection method is inadequate because it does not take traffic and load conditions into account. This leads to low system utilization. As a result, many more calls are blocked than is necessary and reduced revenues for the system service provider results.
The First Available Route Without Resequencing method makes route selections dependent on traffic conditions. However, it is slow in setting up calls because of the exhaustive nature of the search. Furthermore, the method can not be implemented in systems that do not support the fast exchange of route search control signals.
What is needed to overcome the deficiencies of methods known in prior art is a route selection method and apparatus that must:
a) fully utilize the available system resources to support as many calls as possible, PA1 b) provide robust system performance under a wide range of traffic and load conditions, PA1 c) be simple to implement and have low traffic overhead, and PA1 d) have practical utility in a wide range of communication systems.